package leetcode;

import java.util.HashMap;

public class sixteen2 {
    //这个解法的错误是
    public static boolean is_right(HashMap<Character,Integer> hashMap1,HashMap<Character,Integer> hashMap) {
        boolean containsAll=true;
        for(char key:hashMap.keySet()){
            if(hashMap1.getOrDefault(key,0)<hashMap.get(key)){
                containsAll=false;
                break;
            }
        }
        return containsAll;


    }
    public static String minWindow(String s, String t) {
        int m=s.length();
        int n=t.length();
        if(m<n){
            return "";
        }
        HashMap<Character,Integer> hashMap=new HashMap<>();
        for(int i=0;i<n;i++){
            char in=t.charAt(i);
            hashMap.put(in,hashMap.getOrDefault(in,0)+1);
        }
        int left;
        int right;
        String minWindow="";
        int minlength=Integer.MAX_VALUE;
        HashMap<Character,Integer> hashMap1=new HashMap<>();
        for(left=0,right=0;right<m;right++){
            char in1=s.charAt(right);
            hashMap1.put(in1,hashMap1.getOrDefault(in1,0)+1);
//            boolean containsAll=true;
//            for(char key:hashMap.keySet()){
//                if(hashMap1.getOrDefault(key,0)<hashMap.get(key)){
//                    containsAll=false;
//                    break;
//                }
//            }
//            boolean right1 = is_right(hashMap1, hashMap);
//            if(right1&&right-left+1<minlength){
//                minlength=right-left+1;
//                minWindow=s.substring(left,right+1);
//            }
//            while(right1){
//                char out=s.charAt(left);
//                hashMap1.put(out,hashMap1.get(out)-1);
//                if(hashMap1.get(out)==0){
//                    hashMap1.remove(out);
//                }
//                left++;
//                if(!is_right(hashMap1,hashMap)){
//                    break;
//                }
//            }
            while(is_right(hashMap1,hashMap)){
                if(right-left+1<minlength){
                    minlength=right-left+1;
                    minWindow=s.substring(left,right+1);
                }
                char out=s.charAt(left);
                hashMap1.put(out,hashMap1.get(out)-1);
                if(hashMap1.get(out)==0){
                    hashMap1.remove(out);
                }
                left++;
            }
        }
        return minWindow;

    }
    public static void main(String[] args) {
//        s = "ADOBECODEBANC", t = "ABC"
//        s = "aabbcc"
//        t = "abc"
//        s = "xyyzyzyx"
//        t = "xyz"
        String s="ADOBECODEBANC";
        String t="ABC";
        String s1 = minWindow(s, t);
        System.out.println(s1);
    }

}
